public class dp {
    /**
     * 一只青蛙一次可以跳上1级台阶,也可以跳上2级,
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)
     */

    /**
     * 动态规划:
     * 1.定义状态
     * 2.编写状态转移方程
     * 3.设置初始值
     */
    public int JumpFloor1(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 2; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }

    public int JumpFloor2(int target) {
        int first = 1;
        int second = 1;
        int third = 1;
        for (int i = 2; i <= target; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

    /**
     * 我们可以使用 2*1 的小矩形横着或者竖着去覆盖更大的矩形,请问用n个2*1 的小矩形无重叠的覆盖一个 2*n 的大矩形
     * 总共有多少种方法
     * 比如:n=3 时,2*3 的矩形有3 中覆盖方法:
     */
    /**
     * 动态规划:
     * 1.定义状态
     * 2.编写状态转移方程
     * 3.设置初始值
     * 用 n 个 2*1 的小矩形无重叠的覆盖一个2*n 的大矩形,每次放置的时候,无非两种方法:
     * 其中,横着放一个之后,下一个的方法已确定,虽然放置了两个矩形,但属于同一种放法
     * 竖着放一个之后,本轮放置已经完成,也属于一种方法
     * 所以当2*n 的大矩形被放慢的时候,就是用以上两种方式来放的
     * 用dp 法来解决:
     * 状态定义:f(n):用n个2*1的小矩形无重叠的覆盖一个2*n的大矩形所用的总方法数
     * 状态方程: f(n) = f(n-1)[最后一个竖着放]+f(n-2)[最后两个横着放]
     * 初始化:f(1)=1,f(2)=2,f(0)=1,注意,可以不考虑f(0)
     */
    public int rectCover(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];

        }
        return dp[target];
    }
    /**
     * {6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8
     * (从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，
     * 动态规划 :
     * 定义状态 :f(i) 以i 下标结尾的最大连续子序列的和
     * 状态递推:f(i) = max(f(i-1)+array[i],array[i])
     * 状态初始化:f(0) = array[0] max = array[0]
     */
    public int FindGreatestSumOfSubArray(int[] array) {

        int[] dp = new int[array.length];
        dp[0] = array[0];
        int maxValue = array[0];
        for (int i = 0; i < array.length; i++) {
            dp[i] = Math.max(dp[i-1] + array[i],array[i]);
            if (maxValue < dp[i]) {
                maxValue = dp[i];
            }
        }
        return maxValue;
    }

    /**
     * 最小花费爬楼梯
     * 给定一个整数数组 cost  ，其中
     * cost[i]  是从楼梯第 i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * 请你计算并返回达到楼梯顶部的最低花费。
     */
    public int minCostClimbingStairs (int[] cost) {
        int[] dp = new int[cost.length + 1];
        for (int i = 2;i <= cost.length;i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);
        }
        return dp[cost.length];

    }
}
